/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann Tübingen, Germany 
 * Niko Schenk Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package collectors.impl;

import collectors.impl.visitors.CollectTraversal;
import collectors.api.Collector1;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import util.tokenization_io.BoundarySymbols;
import util.Interval;
import saphre.core.Store;
import saphre.core.SuffixArray;
import java.util.*;
import saphre.commands.CmdGappyParameters;
import util.sorting.Multiset;
import util.statistics.Ngram;
import util.statistics.StatisticsHandler;
import util.IntString;
import util.IntStringMultiset;

/**
 * Class which simulates lcp-interval tree traversal to collect GAPPY PHRASES.
 * It implements the Collector1 interface.
 *
 * Collect the RIGHT part of a phrase.
 *
 *
 * @authors Dale Gerdemann, Niko Schenk
 */
public class GappyPhrasesRightPartPrintCollector implements Collector1 {

    //private static List<Set<IntString>> contextNo2Alts = new ArrayList<Set<IntString>>();
    private static Map<IntString, Set<Integer>> alt2ContextId = new TreeMap<IntString, Set<Integer>>();
    private static int contextNo = -1;
    private static Store store;
    private static List<Multiset> ddOfContext = new ArrayList<Multiset>();
    private static double D;
    private BoundarySymbols tc;
    private SuffixArray sa2;
    private Interval top;
    private int[] leftPart;
    private Set<Integer> leftStart;
    private boolean alreadyFoundRightPartBeforeNow = false;
    private SuffixArray sa;
    private SuffixArray pa;
    private CmdGappyParameters gappyParameters;
    private PrintWriter gW;
    private Map<String, Ngram> ngramMap;
    private DecimalFormat df = new DecimalFormat("#.#####");

    /**
     *
     * @param leftPart
     * @param leftStart
     * @param store
     * @param sa2
     * @param top
     * @param sa
     * @param pa
     * @param gappyParameters
     * @param ngramMap
     */
    public GappyPhrasesRightPartPrintCollector(int[] leftPart, Set<Integer> leftStart, Store store,
            SuffixArray sa2, Interval top, SuffixArray sa, SuffixArray pa,
            CmdGappyParameters gappyParameters, PrintWriter gW, Map ngramMap) {

        this.leftPart = leftPart;
        this.leftStart = leftStart;
        GappyPhrasesRightPartPrintCollector.store = store;
        tc = store.getTC();
        this.sa2 = sa2;
        this.top = top;
        this.sa = sa;
        this.pa = pa;
        D = (double) store.numDocs() - 1;
        CollectTraversal.pseudoDepth = 0;

        this.gappyParameters = gappyParameters;
        this.gW = gW;
        this.ngramMap = ngramMap;

    }

    /*
     * 
     */
    public boolean foundRightPart() {
        return alreadyFoundRightPartBeforeNow;
    }

    /**
     *
     * @param inter
     * @param parentLcp
     * @param lcp
     * @param depth
     */
    @Override
    public void preAdd(Interval inter, int parentLcp, int lcp, int depth) {
    }

    /**
     *
     * @param inter
     * @param lcp
     * @param depth
     * @param docDist
     * @param leftContext
     */
    @Override
    public void add(Interval inter, int lcp, int depth, Multiset docDist,
            Multiset leftContext) {

        int[] suftab = sa2.getSuftab();
        int loc = suftab[inter.lb()];
        Set<Integer> rightEnd = new TreeSet<Integer>();
        for (int i = inter.lb(); i <= inter.rb(); i++) {
            rightEnd.add(suftab[i]);
        }
        Set<Integer> innerLeft = new HashSet<Integer>();
        Set<Integer> innerRight = new HashSet<Integer>();

        // Get the fillers!
        Map<IntString, Set<Integer>> bridge =
                makeBridge(leftStart, rightEnd, innerLeft, innerRight);
        int[] rightPart = new int[0];
        rightPart = store.toArray(loc, loc + lcp);

        // Put a filter on the fillers.
        bridge = filterBridge(bridge, leftPart, rightPart);

        String rightPartStr = store.toString(rightPart);
        //System.out.println(rightPartStr + "-> " + sa.search(rightPart).tf());

        if (innerLeft.size() > 1 && innerRight.size() > 1) {
            String leftPartStr = store.toString(leftPart);
            //System.out.println("leftPartStr->" + leftPartStr + "<-");
            //System.out.println("inleftPart->" + inLeftPart);

            // Most frequent filler and...
            IntString[] winner = new IntString[1];
            // ... its term frequency.
            int[] winnerFreq = new int[1];

            // Term frequency of the gappy phrase.
            int numGappyComponents = numGappyComponents(bridge);
            // Document frequency of the gappy phrase.
            Multiset docDistBr = dfOfGappyPhrase(bridge);
            int dfOfGappyPhrase = docDistBr.size();

            // Check if there is a single most frequent filler.
            boolean tie = tfDistribution(bridge, winner, winnerFreq);

            // Get the percentage of maximal fillers.
            double maxFill = getMaxFill(bridge);

            // Idea: PREcompute term frequencies for all n-grams of length 
            // gapMin to gapMax, i.e. for all potential fillers in a separate traversal.
            // This way, we can apply some dynamic programming style and avoid
            // unnecessary recomputation of the term frequencies for the same fillers
            // over and over again.
            // TODO: REFACTOR SIMILAR SOURCE CODE !!!


            //**** Left part.
            int tfLeftPart;
            int dfLeftPart;
            Ngram ngramObjectLeftPart = ngramMap.get(leftPartStr);
            if (ngramObjectLeftPart != null) {
                tfLeftPart = ngramObjectLeftPart.getTf();
                dfLeftPart = ngramObjectLeftPart.getDf();
            } else {
                Interval leftPartInter = sa.search(leftPart);
                tfLeftPart = leftPartInter.tf();
                dfLeftPart = leftPartInter.df(sa, store);
                // add to map.
                Ngram ngramLeftPart = new Ngram();
                ngramLeftPart.setTf(tfLeftPart);
                ngramLeftPart.setDf(dfLeftPart);
                ngramMap.put(leftPartStr, ngramLeftPart);
            }

            //**** Right part.
            int tfRightPart;
            int dfRightPart;
            Ngram ngramObjectRightPart = ngramMap.get(rightPartStr);
            if (ngramObjectRightPart != null) {
                tfRightPart = ngramObjectRightPart.getTf();
                dfRightPart = ngramObjectRightPart.getDf();
            } else {
                Interval rightPartInter = sa.search(rightPart);
                tfRightPart = rightPartInter.tf();
                dfRightPart = rightPartInter.df(sa, store);
                // add to map.
                Ngram ngramRightPart = new Ngram();
                ngramRightPart.setTf(tfRightPart);
                ngramRightPart.setDf(dfRightPart);
                ngramMap.put(rightPartStr, ngramRightPart);
            }


            // TODO: Find an alternative way to compute the mutual information of a 
            // discontinuous phrase. Question: Which parts should be considered 
            // for the computation of mutual information?
            // How about computing the mutual information of a gapped phrase
            // as the average of all n-grams including left - fillers - and right context?


            // One way: Take gappy phrase as a whole (sum tf of all fillers, i.e.
            // the term frequency of all gappy phrase components with the two contexts)
            // and use the contexts to compute the mutual information. 
            double miLeftRightPart = StatisticsHandler.mi(numGappyComponents, leftPart, rightPart, sa);

            // An alternative computation of the mutual information of a gappy phrase would be
            // to average over the mutual information scores of each gapped component, e.g.
            // this [nice|lovely] day     has two components
            // this nice day     and     this lovely day.
            // Mi is computed separately for each (in this case) trigram and then 
            // summed + divided by the number of distinct fillers.

            // Assemble gappy phrase.
            //for(IntString f : bridge.keySet()) {
            //    System.out.println("-> " + store.toString(leftPart) + "-" + store.toString(f) + "-" + store.toString(rightPart)); 
            //}

            // Same idea but different computation of mi.
            // Do the same for Y & C computation.
            double miAverageOverAllGappyComponentsYamamotoChurch = StatisticsHandler.computeAverageMiForGappyComponents(leftPart, bridge, rightPart, sa);


            // Get a list of separate gappy components.
            //System.out.println(miAverageOverAllGappyComponentsYamamotoChurch);

            double ridfLeftPart = StatisticsHandler.ridf(tfLeftPart, dfLeftPart, D);
            double ridfRightPart = StatisticsHandler.ridf(tfRightPart, dfRightPart, D);


            double ridfGappyPhrase = StatisticsHandler.ridf(numGappyComponents, docDistBr, D);


//            System.out.println(miLeftRightPart + ">=" + minMiLeftRightPart + "\n"
//                    + miAverageOverAllGappyComponentsYamamotoChurch + ">=" + minCombinedAverageMiYamamotoChurch + "\n" +
//                    ridfGappyPhrase + ">=" + minGlobalRidf + "\n"+
//                    numGappyComponents + ">=" + minTfOfGappyPhrase + "\n"+
//                    dfOfGappyPhrase + ">=" + minDfOfGappyPhrase + "\n"+
//                    leftPart.length + ">=" + minLengthOfLeftPart + "\n"+
//                    leftPart.length + "<=" + maxLengthOfLeftPart + "\n"+
//                    tfLeftPart + ">=" + minTfOfLeftPartInCorpus + "\n"+
//                    ridfLeftPart + ">=" + minRidfOfLeftPartInCorpus + "\n"+
//                    rightPart.length + ">=" + minLengthOfRightPart + "\n"+
//                    tfRightPart + ">=" + minTfOfRightPartInCorpus  + "\n"+
//                    ridfRightPart + ">=" + minRidfOfRightPartInCorpus + "\n"+
//                    bridge.size() + ">=" + minNumberOfFillers + "\n"+
//                    sumTfOfFillers + ">=" + minSumTfOfFillers + "\n"+
//                    avgRidfOfFillers + ">=" + minAverageRidfOfFillers + "\n"+
//                    maxFill + ">=" + minMaxfill);


            // Condition on the parameters here.
            if ( // General.
                    miLeftRightPart >= gappyParameters.getMinMiLeftRightPart()
                    && miAverageOverAllGappyComponentsYamamotoChurch >= gappyParameters.getMinCombinedAverageMiYamamotoChurch()
                    && ridfGappyPhrase >= gappyParameters.getMinGlobalRidf()
                    && numGappyComponents >= gappyParameters.getMinTfOfGappyPhrase() && // tf of gappy phrase.
                    dfOfGappyPhrase >= gappyParameters.getMinDfOfGappyPhrase()
                    && // df of gappy phrase.
                    // Left part.
                    leftPart.length >= gappyParameters.getMinLengthOfLeftPart()
                    && leftPart.length <= gappyParameters.getMaxLengthOfLeftPart()
                    && tfLeftPart >= gappyParameters.getMinTfOfLeftPartInCorpus()
                    && tfLeftPart <= gappyParameters.getMaxTfOfLeftPartInCorpus()
                    && ridfLeftPart >= gappyParameters.getMinRidfOfLeftPartInCorpus()
                    && leftPartStr.contains(gappyParameters.getInLeftPart())
                    && // Right part.
                    rightPart.length >= gappyParameters.getMinLengthOfRightPart()
                    && rightPart.length <= gappyParameters.getMaxLengthOfRightPart()
                    && tfRightPart >= gappyParameters.getMinTfOfRightPartInCorpus()
                    && tfRightPart <= gappyParameters.getMaxTfOfRightPartInCorpus()
                    && ridfRightPart >= gappyParameters.getMinRidfOfRightPartInCorpus()
                    && rightPartStr.contains(gappyParameters.getInRightPart())
                    && // Fillers.
                    bridge.size() >= gappyParameters.getMinNumberOfFillers()
                    && // number of fillers
                    maxFill >= gappyParameters.getMinMaxfill()
                    && isSubstringInOneOfFillers(bridge, gappyParameters.getInOneOfFillers())) {


                // This is costly.
                double[] rval = StatisticsHandler.computeSumTFAndAverageRidfOfFillers(bridge, sa, store, D, ngramMap);
                double sumTfOfFillers = rval[0];
                double avgRidfOfFillers = rval[1];
                double ratio = (double) (sumTfOfFillers / bridge.size());

                if (sumTfOfFillers >= gappyParameters.getMinSumTfOfFillers()
                        && avgRidfOfFillers >= gappyParameters.getMinAverageRidfOfFillers()
                        && ratio >= gappyParameters.getMinRatio()) {

                    if (!alreadyFoundRightPartBeforeNow) {
                        String s = "\n-------------------" + leftPartStr
                                + "----------------------\n";
                        System.out.print(s);
                        if (gW != null) {
                            gW.write(s);
                        }
                    }

                    alreadyFoundRightPartBeforeNow = true;

                    // Get the gappy phrase.
                    String gappyPhrase =
                            "-->\t\t" + leftPartStr + " "
                            // + bars(bridge.keySet())
                            + barsAlt(bridge) + " "
                            + rightPartStr + "\n";

                    // Uncomment this if you need to get the document
                    // distribution of this gappy phrase.
                    //String docDistGappyPhrase = docDistBr.toStringDF(store);

                    System.out.printf(
                            "MaxFill:%2.4f\t"
                            + "MIleft&right:%2.4f\t"
                            + "MIavgGappys:%2.4f\t"
                            + "RIDFglobal:%2.4f\t"
                            + "RIDFavgFillers:%2.4f\t"
                            + "dfGappyPhrase:%2.1f\t"
                            + "NumGappyComponents:%2.1f\t"
                            + "SumTfOfFillers:%2.1f\t"
                            + "NumFillers/SumTfOfFillers:%2.4f " + "\n",
                            maxFill,
                            miLeftRightPart,
                            miAverageOverAllGappyComponentsYamamotoChurch,
                            ridfGappyPhrase,
                            avgRidfOfFillers,
                            (double) dfOfGappyPhrase,
                            (double) numGappyComponents,
                            (double) sumTfOfFillers,
                            ratio);

                    System.out.println(gappyPhrase);



                    if (!tie) {
                        String win = "Most frequent filler: " + store.toString(winner[0]) + ":"
                                + winnerFreq[0] + "\n";
                        System.out.println();
                        System.out.print(win);

                        if (gW != null) {
                            gW.write(win);
                        }
                    }

                    if (gW != null) {
                        String stringToFile =
                                " MaxFill: " + df.format(maxFill)
                                + " MIleft&right: " + df.format(miLeftRightPart)
                                + " MIavfGappys: " + df.format(miAverageOverAllGappyComponentsYamamotoChurch)
                                + " RIDFglobal: " + df.format(ridfGappyPhrase)
                                + " RIDFavgFillers: " + df.format(avgRidfOfFillers)
                                //+ docDistBr.toStringDF(store) 
                                + " dfGappyPhrase: " + dfOfGappyPhrase
                                + " NumGappyComponents: " + numGappyComponents
                                + " SumTfOfFillers: " + sumTfOfFillers
                                + " NumFillers/SumTfOfFillers: " + ratio + "\n";
                        gW.write(stringToFile);
                        gW.write(gappyPhrase);
                        gW.write("\n");
                    }

                    
                    docDistBr.addTo(ddOfContext.get(contextNo));
                }
            } else {
//                System.out.println("Filtering gappy phrase:");
//                System.out.print(leftPartStr + " --- ");
//                for(IntString f : bridge.keySet()) {
//                    System.out.print(store.toString(f) + "|");
//                }
//                System.out.println(" --- " + rightPartStr);
            }
            if (gW != null) {
                gW.flush();
            }
        }
    }

    /**
     *
     * @param inter
     * @param lcp
     * @param depth
     * @param docDist
     * @param leftContext
     */
    @Override
    public void addTrivial(Interval inter, int lcp, int depth,
            Multiset docDist, Multiset leftContext) {
    }

    /*
     * Filter the fillers.
     * (bridge construction)
     */
    private Map<IntString, Set<Integer>> filterBridge(Map<IntString, Set<Integer>> bridge,
            int[] leftPart, int[] rightPart) {
        Multiset fullRightContext = new Multiset();
        Multiset fullLeftContext = new Multiset();
        for (IntString i : bridge.keySet()) {
            for (int j : bridge.get(i)) {
                int tok = sa.getText()[j + rightPart.length];
                fullRightContext.incr(tok);
                tok = sa.getText()[j - i.length() - leftPart.length - 1];
                fullLeftContext.incr(tok);
            }
        }

        Map<IntString, Set<Integer>> bridge1 =
                new TreeMap<IntString, Set<Integer>>();
        IntStringMultiset filtered = new IntStringMultiset();
        for (IntString i : bridge.keySet()) {
            Multiset rightContext = new Multiset();
            Multiset leftContext = new Multiset();
            for (int j : bridge.get(i)) {
                int tok = sa.getText()[j + rightPart.length];
                rightContext.incr(tok);
                tok = sa.getText()[j - i.length() - leftPart.length - 1];
                leftContext.incr(tok);
            }

            boolean countThis = true;
            for (int j : bridge.get(i)) {
                int tok = sa.getText()[j + rightPart.length];
                if (rightContext.cnt(tok) > 1) {
                    countThis = false;
                }
                tok = sa.getText()[j - i.length() - leftPart.length - 1];
                if (leftContext.cnt(tok) > 1) {
                    countThis = false;
                }
                if (countThis) {
                    Set<Integer> occur = bridge1.get(i);
                    if (occur == null) {
                        occur = new TreeSet<Integer>();
                        bridge1.put(i, occur);
                    }
                    occur.add(j);
                    filtered.incr(i);
                }
            }
        }
        return bridge1;
    }

    /*
     * Get the fillers!
     * (bridge construction)
     */
    private Map<IntString, Set<Integer>> makeBridge(Set<Integer> left, Set<Integer> right,
            Set<Integer> innerLeft, Set<Integer> innerRight) {

        Map<IntString, Set<Integer>> result = new TreeMap<IntString, Set<Integer>>();
        Iterator<Integer> r = right.iterator();
        int prevR = r.next().intValue();
        int minGap = gappyParameters.getMinGap();
        int maxGap = gappyParameters.getMaxGap();
        for (int i = minGap; i <= maxGap; i++) {
            if (left.contains(prevR - i)) {
                if (!reject(prevR - i, prevR)) {
                    IntString alt = store.toIntString(prevR - i, prevR);
                    if (alt.length() > 0) {
                        innerLeft.add(store.text[prevR - i]);
                        innerRight.add(store.text[prevR - 1]);
                    }
                    Set<Integer> occur = result.get(alt);
                    if (occur == null) {
                        occur = new HashSet<Integer>();
                        result.put(alt, occur);
                    }
                    occur.add(prevR);
                }
                break;
            }
        }
        while (r.hasNext()) {
            int nextR = r.next().intValue();
            int rGap = nextR - prevR;
            for (int i = minGap; i <= Math.min(rGap, maxGap); i++) {
                if (left.contains(nextR - i)) {
                    if (!reject(nextR - i, nextR)) {
                        IntString alt = store.toIntString(nextR - i, nextR);
                        if (alt.length() > 0) {
                            innerLeft.add(store.text[nextR - i]);
                            innerRight.add(store.text[nextR - 1]);
                        }
                        Set<Integer> occur = result.get(alt);
                        if (occur == null) {
                            occur = new HashSet<Integer>();
                            result.put(alt, occur);
                        }
                        occur.add(nextR);
                    }
                    prevR = nextR;
                    break;
                }

            }
        }
        return result;
    }

    /*
     * Print fillers.
     */
    private String bars(Set<IntString> s) {
        if (s.size() == 0) {
            return "[]";
        }
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        Iterator<IntString> r = s.iterator();
        sb.append(store.toString(r.next()));

        String sx = store.toString(r.next());
        while (r.hasNext()) {
            sb.append("|");
            sx = store.toString(r.next());
            // System.out.println(sx);
            sb.append(sx);
        }
        sb.append("]");
        return sb.toString();
    }

    /*
     * Print fillers.
     * (alternative form)
     */
    private String barsAlt(Map<IntString, Set<Integer>> m) {
        contextNo++;
        ddOfContext.add(new Multiset());

        Set<IntString> sis = new TreeSet<IntString>();
        //contextNo2Alts.add(sis);

        Set<IntString> s = m.keySet();
        if (s.size() == 0) {
            return "[]";
        }
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        Iterator<IntString> r = s.iterator();

        IntString rn = r.next();
        String sx = store.toString(rn);
        sb.append(sx);
        Set<Integer> contextNos = alt2ContextId.get(rn);
        if (contextNos == null) {
            contextNos = new TreeSet<Integer>();
            alt2ContextId.put(rn, contextNos);
        }
        contextNos.add(contextNo);
        sis.add(rn);
        while (r.hasNext()) {
            sb.append("|");
            rn = r.next();
            sx = store.toString(rn);
            sb.append(sx);

            contextNos = alt2ContextId.get(rn);
            if (contextNos == null) {
                contextNos = new TreeSet<Integer>();
                alt2ContextId.put(rn, contextNos);
            }
            contextNos.add(contextNo);
            sis.add(rn);
        }
        sb.append("]");
        return sb.toString();
    }

    /*
     * 
     */
    private boolean reject(int begin, int end) {
        for (int i = begin; i < end; i++) {
            if (tc.userSentinel(store.text[i])) {
                return true;
            }
        }
        return false;
    }

    /*
     * 
     */
    private int countOnes(String s) {
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                sum++;
            }
        }
        return sum;
    }

    /*
     * Check if a string is a substring of one of the fillers
     */
    private boolean isSubstringInOneOfFillers(Map<IntString, Set<Integer>> bridge, String check) {
        boolean found = false;
        for (IntString is : bridge.keySet()) {
            String aFiller = store.toString(is);
            if (aFiller.contains(check)) {
                found = true;
            }
        }
        return found;
    }

    /*
     * Check if there is a single most frequent filler.
     * Here, "tie" means that at least two fillers have the same 
     * highest term frequency among all fillers.
     * NOT "tie" means that there is a SINGLE most frequent one.
     */
    private boolean tfDistribution(Map<IntString, Set<Integer>> bridge,
            IntString[] winner, int[] winnerFreq) {
        boolean tie = true;
        for (IntString s : bridge.keySet()) {
            int freq = bridge.get(s).size();
            //System.out.println("Filler: " + store.toString(s) + " tf: " + freq);
            if (freq > winnerFreq[0]) {
                tie = false;
                winnerFreq[0] = freq;
                winner[0] = s;
            } else if (freq == winnerFreq[0]) {
                tie = true;
            }
        }
        return tie;
    }

    /*
     * Get the number of gappy components.
     * This method computes the "overall term frequency" of a gappy phrase.
     * Each gappy phrase consits of a number of single gappy components.
     * For example, the gappy phrase "a [nice|lovely] day"
     * could consist of 5 gappy components in total, i.e.
     * 2 times "a nice day" and 3 times "a lovely day".
     */
    private int numGappyComponents(Map<IntString, Set<Integer>> bridge) {
        int result = 0;
        for (Set<Integer> s : bridge.values()) {
            result += s.size();
        }
        return result;
    }

    /*
     * Document frequency of gappy phrase.
     * @param bridge
     * @return 
     */
    private Multiset dfOfGappyPhrase(Map<IntString, Set<Integer>> bridge) {
        Multiset result = new Multiset();
        for (Set<Integer> s : bridge.values()) {
            for (Integer i : s) {
                result.incr(store.docNum(i.intValue()));
            }
        }
        return result;
    }

    /*
     * Check maximality.
     */
    private String isMax(Map<IntString, Set<Integer>> bridge) {
        StringBuilder sb = new StringBuilder();
        for (IntString s : bridge.keySet()) {
            char b = SuffixArray.isMaximal(s.toArray(), top, sa, pa, store)
                    ? '1' : '0';
            sb.append(b);
        }
        return sb.toString();
    }

    /*
     * Get percentage of maximal fillers for a gappy phrase.
     */
    private double getMaxFill(Map<IntString, Set<Integer>> bridge) {
        String im = isMax(bridge); // bit string of maximals.
        // Percentage of maximal fillers, i.e.
        // number of all maximals "ones" divided by all fillers.
        double maxFill = countOnes(im) / (double) im.length();
        return maxFill;
    }
}
